package LeetcodeTest_twenty_six;
//奇偶树

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class isEvenOddTree
{
    public static void main(String[] args)
    {
        TreeNode root=new TreeNode();
        root=solution.createTree(root);
        System.out.println(solution.isEvenOddTree(root));
    }
}
class solution
{
    public static boolean flag=true;
    public static boolean isEvenOddTree(TreeNode root)
    {
        int i,j,x;
        int count,current,next;
        boolean answer=true;
        ArrayList<Integer> list=new ArrayList<Integer>();
        ArrayList<Integer> nums=new ArrayList<Integer>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        current=x=1;
        count=next=0;
        queue.offer(root);
        while(!queue.isEmpty())
        {

            TreeNode tree=queue.poll();
            current--;
            if(tree.left!=null)
            {
                queue.offer(tree.left);
                next++;
            }
            if(tree.right!=null)
            {
                queue.offer(tree.right);
                next++;
            }
            list.add(tree.val);
            if(current==0)
            {
                for(i= list.size()-x;i<=list.size()-1;i++)
                    nums.add(list.get(i));
                for(j=0;j<nums.size();j++)
                {
                    if(count%2==0)
                    {
                        if(nums.get(j)%2!=0)
                        {
                            if(j==nums.size()-1)
                                flag=true;
                            else if(j+1<nums.size() && nums.get(j)<nums.get(j+1))
                            {
                                flag = true;
                            }
                            else
                            {
                                flag = false;
                                answer=flag;
                                flag=true;
                                System.out.println(121);
                                return answer;
                            }
                        }
                        else
                        {
                            flag = false;
                            answer=flag;
                            flag=true;
                            System.out.println(122);
                            return answer;
                        }
                    }
                    else
                    {
                        if(nums.get(j)%2==0)
                        {
                            if(j==nums.size()-1)
                                flag=true;
                            else if(j+1<nums.size() && nums.get(j)>nums.get(j+1))
                            {
                                flag=true;
                            }
                            else
                            {
                                flag = false;
                                answer=flag;
                                flag=true;
                                System.out.println(123);
                                return answer;
                            }
                        }
                        else
                        {
                            flag = false;
                            answer=flag;
                            flag=true;
                            System.out.println(124);
                            return answer;
                        }
                    }
                }
                count++;
                nums.clear();
                current=next;
                x=current;
                next=0;
            }
        }
        return answer;
    }
    public static TreeNode createTree(TreeNode T)
    {
        Scanner reader=new Scanner(System.in);
        int a=reader.nextInt();
        TreeNode p=null;
        if (a==-1)
            p=null;
        else
            p = new TreeNode(a);
        T=p;
        if(T==null)
            return T;
        else
        {
            T.left = createTree(T.left);
            T.right = createTree(T.right);
        }
        return T;
    }
}